import java.util.*;
/*
 * 表达式求值
 * 
 * 描述

请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：
0
≤
∣
s
∣
≤
100
0≤∣s∣≤100，保证计算结果始终在整型范围内

要求：空间复杂度： 
O
(
n
)
O(n)，时间复杂度 
O
(
n
)
O(n)
 */
public class 表达式求值 {
    
    public static void main(String[] args) {
        


    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public static int solve (String s) {
        // write code here

        // write code here
       String str = s.replaceAll(" ", "");
       char[] cs = str.toCharArray();
       int n = str.length();
       // 存放所有的数字
       Deque<Integer> nums = new ArrayDeque<>();
       // 为防止第一个数是负数，先往nums加个0
       nums.offer(0);
       //存放所有非数字意外的操作
       Deque<Character> ops = new ArrayDeque<>();
        
       for (int i = 0; i < n; i++) {
           // 取第一个字符
           char c = cs[i];
           if (c == '(') {
               ops.offer(c);
           } else if(c == ')') {
               // 计算到最近一个左括号为止
               while (!ops.isEmpty()) {
                   if (ops.peekLast() != '(') {
                       // 不是左括号，则是计算符
                       calc(nums, ops);
                   }else {
                       // 是左括号,是空的，移除
                       ops.pollLast();
                       break;
                   }
               }
           } else {
               // 是符号 或者 数字
               if (isNumber(c)) {
                   // 是数字
                   int u = 0;
                   // 当前数字的下标
                   int j = i;
                   // 将从i 位置开始后面的连续数字整体取出， 加入 nums
                   while(j < n && isNumber(cs[j])) {
                       u = u * 10 + (cs[j++] -'0');
                   }
                   nums.addLast(u);
                   i = j - 1;
                    
               }else {
                   // 是字符 有一个新操作要入栈时，先把栈内可以算的都算了
                   // 只有满足 【栈内运算符】 比 【当前运算符】 优先级高 / 同等， 才进行运算
                   if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
                       nums.addLast(0);
                   }
                   while (!ops.isEmpty() && ops.peekLast() != '(') {
                       char prev = ops.peekLast();
                       if (map.get(prev) >= map.get(c)) {
                           calc(nums, ops);
                       }else {
                           break;
                       }
                   }
                   ops.addLast(c);
               }
           }
       }
       // 将剩余的计算完
       while (!ops.isEmpty() && ops.peekLast() != '(') {
           calc(nums, ops);
       }
       return nums.peekLast();

    }

    static void calc(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) return;
        if (ops.isEmpty()) return;
        int b = nums.pollLast();
        int a = nums.pollLast();
        // 获取最后一个操作符
        char op = ops.pollLast();
        int ans = 0;
        if (op == '+') ans = a + b;
        else if (op == '-') ans = a - b;
        else if (op == '*') ans = a * b;
        nums.addLast(ans);
    }
    
    static boolean isNumber(char c) {
        return Character.isDigit(c);
    }

    // 使用map 维护一个运算符优先级（其中减法优先级相同，乘法有着更高的优先级）
   static Map<Character, Integer> map = new HashMap<Character, Integer>(){{
        put('-', 1);
        put('+', 1);
        put('*', 2);
    }};
}
